ბელმან ფორდის (Bellman-Ford)
ალგორითმი უმოკლესი გზების
საპოვნელად
მარიამ გობრონიძე

ზოგადი წონიანი გრაფისთვის ერთ წვეროდან ყველა წვერომდე უმოკლესი ბილიკის
პოვნა შესაძლებელია Bellman–Ford-ის ალგორითმით დროით O(VE). თუ გრაფში
უარყოფითი წონები არ გვხვდება, უკეთესი შედეგის მიღება შესაძლებელია Dijkstra-ს
ალგორითმით დროით O(E + V log V).
შესაძლებელია კიდევ უფრო ეფექტური ალგორითმის გამოყენება მიმართული და
აციკლური გრაფებისთვის. კონკრეტულად კი, უმოკლესი ბილიკების პოვნა
შესაძლებელია O(V + E) დროში, ტოპოლოგიური დალაგების გამოყენებით

ვთქვათ მოცემულია წონიანი გრაფი V წვეროთი და E წიბოთა სიმრავლით
(საწყისი წვერი src).
ამოცანა
ვიპოვოთ მინიმალური მანძილები საწყისი წვერიდან ყველა დანარჩენ
წვერამდე. იმ შემთხვევაში, თუ წვერი მიუწვდომელია საწყისი წერტილიდან,
მანძილს აღვნიშნავთ – 10^8. თუ გრაფში არსებობს უარყოფითი წონის
ციკლი, უნდა დავაბრუნოთ -1, რაც მიუთითებს, რომ უმოკლესი გზის
პოვნა შეუძლებელია.

განმარტება :
მინიმალური გზები:
●

0→1=5

●

0→1→2=6

●

0→1→2→4→3=6

●

0→1→2→4=7

გრაფი შეიცავს უარყოფითი წონის ციკლს : 1 → 2 → 3 → 1, სადაც ციკლის ჯამური
წონა უარყოფითია .

უარყოფითი წონის ციკლი:
ეს არის ციკლი გრაფში, რომლის ყველა წიბოს წონის ჯამი
უარყოფითია. ასეთი ციკლის გავლა ამცირებს მთლიანი გზის წონას
ყოველ მომდევნო გავლაზე, რაც ნიშნავს, რომ უმოკლესი გზა არ
არსებობს (ყოველ ტრავერსიაზე შემცირდება წონა).

დეიქსტრას ალგორითმის შეზღუდვა:
მიუხედავად იმისა, რომ დეიქსტრას ალგორითმი ხშირად გამოიყენება (Single
Source Shortest Path) უმოკლესი გზის პოვნის ამოცანებში, იგი არ გამოდგება
უარყოფითი წონის მქონე გრაფებისათვის. ის არ განაახლებს უკვე
მონახულებული წვეროების მნიშვნელობებს, ამიტომ ვერ აფიქსირებს იმ
შემთხვევას, როდესაც უარყოფითი წონის გარშემო გრძელი ბილიკი იძლევა
იფრო მოკლე გზას.

რელაქსაციის პრინციპი:
რელაქსაცია ნიშნავს წვეროს მანძილის განახლებას, თუ ნაპოვნია უფრო მოკლე
ბილიკი სხვა წვეროს გავლით.
•

თუ გვაქვს წიბო (u, v) წონით w, და distance[v] > distance[u] +
w, მაშინ განვაახლებთ წვეროს შესაბამის წონას შემდეგნაირად:
distance[v] = distance[u] + w

ეს პროცესი ყველა წიბოზე მეორდება (V - 1)-ჯერ.

რატომ არის საკმარისი (V - 1) რაოდენობის
რელაქსაცია ?
Shortest Path შესაძლოა შეიცავდეს მაქსიმუმ (V - 1) წიბოს. თუ ბილიკი შეიცავს
უფრო მეტ წიბოს, ამ შემთხვევაში წარმოიქმნება ციკლი. შესაბამისად, (V - 1)-ჯერ
წიბოების რელაქსაცია საკმარისია ყველა ბილიკის შესამოწმებლად.

უარყოფითი წონის ციკლის აღმოჩენა:
თუ (V - 1)-ჯერ რელაქსაციის შემდეგ შესაძლებელია დამატებითი
რელაქსაცია , ეს ნიშნავს, რომ არსებობს ციკლი, რომლის ჯამური წონა
უარყოფითია. ასეთ შემთხვევაში,Shortest Path არ არსებობს და პასუხად
ვაბრუნებთ -1.

გმადლობთ ყურადღებისთვის!

